package org.example;

import java.util.PriorityQueue;

// 【双指针技巧秒杀七道链表题目】
// 1、合并两个有序链表
// 2、链表的分解
// 3、合并 k 个有序链表
// 4、寻找单链表的倒数第 k 个节点
// 5、寻找单链表的中点
// 6、判断单链表是否包含环并找出环起点
// 7、判断两个单链表是否相交并找出交点
public class DoublePointerToLinkedList {
    static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    // 21. 合并两个有序链表
    // 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
    // 输入：l1 = [1,2,4], l2 = [1,3,4]
    // 输出：[1,1,2,3,4,4]
    static class MergeTwoLists {
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            // 虚拟头结点
            ListNode dummy = new ListNode(-1);
            ListNode p = dummy;
            ListNode p1 = l1;
            ListNode p2 = l2;
            while (p1 != null && p2 != null) {
                // 比较p1和p2两个指针
                // 将值较小的节点接到p指针
                if (p1.val > p2.val) {
                    p.next = p2;
                    p2 = p2.next;
                } else {
                    p.next = p1;
                    p1 = p1.next;
                }
                // p指针不断前进
                p = p.next;
            }
            if (p1 != null) {
                p.next = p1;
            }
            if (p2 != null) {
                p.next = p2;
            }
            return dummy.next;
        }

        // 经常有读者问我，什么时候需要用虚拟头结点？我这里总结下：当你需要创造一条新链表的时候，可以使用虚拟头结点简化边界情况的处理。
        // 比如说，让你把两条有序链表合并成一条新的有序链表，是不是要创造一条新链表？再比你想把一条链表分解成两条链表，是不是也在创造新链表？
        // 这些情况都可以使用虚拟头结点简化边界情况的处理。
    }

    // 86. 分隔链表
    // 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
    // 你应当 保留 两个分区中每个节点的初始相对位置。
    // 输入：head = [1,4,3,2,5,2], x = 3
    // 输出：[1,2,2,4,3,5]
    static class Partition {
        public ListNode partition(ListNode head, int x) {
            // 存放小于x的链表的虚拟头结点
            ListNode dummy1 = new ListNode(-1);
            // 存放大于等于x的链表的虚拟头结点
            ListNode dummy2 = new ListNode(-1);
            // p1,p2指针负责生成结果链表
            ListNode p1 = dummy1;
            ListNode p2 = dummy2;
            // p负责遍历原链表，类似合并两个有序链表的逻辑
            // 这里将一个链表分解成两个链表
            ListNode p = head;
            while (p != null) {
                if (p.val >= x) {
                    p2.next = p;
                    p2 = p2.next;
                } else {
                    p1.next = p;
                    p1 = p1.next;
                }
                // 不断直接让p指针前进
                // p = p2.next;
                // 断开原链表中的每个节点的next指针
                // 如果我们需要把原链表的节点接到新链表上，而不是 new 新节点来组成新链表的话，那么断开节点和原链表之间的链接可能是必要的。
                // 那其实我们可以养成一个好习惯，但凡遇到这种情况，就把原链表的节点断开，这样就不会出错了。
                ListNode temp = p.next;
                p.next = null;
                p = temp;
            }
            // 连接两个链表
            p1.next = dummy2.next;
            return dummy1.next;
        }
    }

    // 23. 合并 K 个升序链表
    // 给你一个链表数组，每个链表都已经按升序排列。
    // 请你将所有链表合并到一个升序链表中，返回合并后的链表。
    // 输入：lists = [[1,4,5],[1,3,4],[2,6]]
    // 输出：[1,1,2,3,4,4,5,6]
    // 解释：链表数组如下：
    // [
    //   1->4->5,
    //   1->3->4,
    //   2->6
    // ]
    // 将它们合并到一个有序链表中得到。
    // 1->1->2->3->4->4->5->6
    // 合并 k 个有序链表的逻辑类似合并两个有序链表，难点在于，如何快速得到 k 个节点中的最小节点，接到结果链表上？
    // 这里我们就要用到优先级队列这种数据结构，把链表节点放入一个最小堆，就可以每次获得 k 个节点中的最小节点。
    static class MergeKLists {
        public ListNode mergeKLists(ListNode[] lists) {
            if (lists.length == 0) {
                return null;
            }
            // 虚拟头结点
            ListNode dummy = new ListNode(-1);
            ListNode p = dummy;
            // 优先级队列，最小堆
            PriorityQueue<ListNode> pq = new PriorityQueue<>(lists.length, (a, b) -> (a.val - b.val));
            // 将k个链表的头结点加入最小堆
            for (ListNode head : lists) {
                if (head != null) {
                    pq.add(head);
                }
            }

            while (!pq.isEmpty()) {
                // 获取最小节点，接到结果链表中
                ListNode node = pq.poll();
                p.next = node;
                if (node.next != null) {
                    pq.add(node.next);
                }
                // p 指针不断前进
                p = p.next;
            }
            return dummy.next;
        }
    }

    // 返回单链表的倒数第k个节点
    static class FindFromEnd {
        ListNode findFromEnd(ListNode head, int k) {
            ListNode p1 = head;
            // p1先走k步
            for (int i = 0; i < k; i++) {
                p1 = p1.next;
            }
            ListNode p2 = head;
            // p1和p2同时走n-k步
            while (p1 != null) {
                p2 = p2.next;
                p1 = p1.next;
            }
            // p2现在指向第n-k+1个节点，即倒数第k个节点
            return p2;
        }
    }

    // 19. 删除链表的倒数第 N 个结点
    static class RemoveNthFromEnd {
        // 自己写的
        public ListNode removeNthFromEnd(ListNode head, int n) {
            ListNode dummy = new ListNode(-1);
            ListNode p = dummy;
            ListNode p1 = head;
            // p1先走n步
            for (int i = 0; i < n; i++) {
                p1 = p1.next;
            }
            ListNode p2 = head;
            while (p1 != null) {
                p.next = p2;
                p = p.next;
                p2 = p2.next;
                p1 = p1.next;
            }
            if (p2 != null) {
                p.next = p2.next;
            }
            return dummy.next;
        }

        public ListNode removeNthFromEnd1(ListNode head, int n) {
            // 虚拟头结点
            ListNode dummy = new ListNode(-1);
            dummy.next = head;
            // 删除倒数第 n 个，要先找倒数第 n + 1 个节点
            ListNode x = findFromEnd(dummy, n + 1);
            // 删掉倒数第 n 个节点
            x.next = x.next.next;
            return dummy.next;
        }

        ListNode findFromEnd(ListNode head, int k) {
            ListNode p1 = head;
            // p1先走k步
            for (int i = 0; i < k; i++) {
                p1 = p1.next;
            }
            ListNode p2 = head;
            // p1和p2同时走n-k步
            while (p1 != null) {
                p2 = p2.next;
                p1 = p1.next;
            }
            // p2现在指向第n-k+1个节点，即倒数第k个节点
            return p2;
        }
    }

    // 876.单链表的中点
    static class MiddleNode {
        public ListNode middleNode(ListNode head) {
            // 快慢指针初始化指向head
            ListNode slow = head;
            ListNode fast = head;
            // 快指针走到末尾时停止
            while (fast != null && fast.next != null) {
                // 慢指针走一步，快指针走两步
                slow = slow.next;
                fast = fast.next.next;
            }
            return slow;
        }
        // 需要注意的是，如果链表长度为偶数，也就是说中点有两个的时候，我们这个解法返回的节点是靠后的那个节点。
    }

    // 判断链表是否包含环
    // 判断链表是否包含环属于经典问题了，解决方案也是用快慢指针：
    // 每当慢指针 slow 前进一步，快指针 fast 就前进两步。
    // 如果 fast 最终能正常走到链表末尾，说明链表中没有环；
    // 如果 fast 走着走着竟然和 slow 相遇了，那肯定是 fast 在链表中转圈了，说明链表中含有环。
    static class HasCycle {
        public boolean hasCycle(ListNode head) {
            // 快慢指针初始化指向head
            ListNode slow = head;
            ListNode fast = head;
            // 快指针走到末尾时停止
            while (fast != null && fast.next != null) {
                // 慢指针走一步，快指针走两步
                slow = slow.next;
                fast = fast.next.next;
                if (slow == fast) {
                    return true;
                }
            }
            return false;
        }
    }

    // 142.环形链表II
    // 给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
    // 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
    // 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
    // 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
    // 不允许修改 链表。
    static class DetectCycle {
        public ListNode detectCycle(ListNode head) {
            ListNode fast = head;
            ListNode slow = head;
            while (fast != null && fast.next != null) {
                fast = fast.next.next;
                slow = slow.next;
                if (fast == slow) {
                    break;
                }
            }
            // 上面的代码类似hasCycle函数
            if (fast == null || fast.next == null) {
                // fast遇到空指针说明没有环
                return null;
            }
            // 重新指向头结点
            slow = head;
            // 快慢指针同步前进，相交点就是环起点
            while (slow != fast) {
                fast = fast.next;
                slow = slow.next;
            }
            return slow;
        }
    }

    // 160. 两个链表是否相交
    // 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
    static class GetIntersectionNode {
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            // p1指向A链表头结点，p2指向B链表的头结点
            ListNode p1 = headA;
            ListNode p2 = headB;
            // 实际的遍历
            // headA=[1,9,1,2,4]
            // headB=[3,2,4]
            // p1=[1,9,1,2,4,3,2,4]
            // p2=[3,2,4,1,9,1,2,4]
            // 这样p1和p2就可以找到相交的点为[2,4]
            while (p1 != p2) {
                // p1走一步，如果走到A链表末尾，转到B链表
                if (p1 == null) {
                    p1 = headB;
                } else {
                    p1 = p1.next;
                }
                // p2走一步，如果走到B链表末尾，转到A链表
                if (p2 == null) {
                    p2 = headA;
                } else {
                    p2 = p2.next;
                }
            }
            return p1;
        }


        // 根据数组构建单链表
        public static ListNode arrayToListNode(int[] arr) {
            if (arr == null || arr.length == 0) {
                return null;
            }
            ListNode dummy = new ListNode(0);
            ListNode current = dummy;
            for (int num : arr) {
                current.next = new ListNode(num);
                current = current.next;
            }
            return dummy.next;
        }

        public static void main(String[] args) {
            int[] arr1 = {1, 9, 1, 2, 4};
            int[] arr2 = {3, 2, 4};

            ListNode list1 = arrayToListNode(arr1);
            ListNode list2 = arrayToListNode(arr2);
            new GetIntersectionNode().getIntersectionNode(list1, list2);
        }
    }
}
